Prefix trees (commonly called “tries”) are ordered data structures that are used extensively in computer science. There are various enhancements to tries that are intended to improve a trie structure's performance when used for longest-prefix searching—identifying the longest match with a search key—such as for IP routing tables.
Tries can also be used in the context of traffic processing. For example, a first trie could be used to identify blacklisted traffic sources. A source address identifier in incoming traffic can be used as a search key into the first trie and, if a match is found in the first trie, the traffic can be determined to be from a blacklisted traffic source and can be dropped immediately. A second trie could be used to identify whitelisted traffic sources. If a match is found between a source address in incoming traffic and a key in the second trie, the traffic can be determined to be from a whitelisted traffic source and can be accepted and processed accordingly. A third trie could be used to identify non-critically blacklisted traffic sources. If a match is found between a source address in incoming traffic and a key in the third trie, the traffic can be determined to be from a non-critically blacklisted traffic source and can be accepted and handled at a low priority or dropped, depending on available system resources. Incoming traffic from a source that is not identified in any of the tries may be treated as being from an untrusted source and may be handled at a low priority, albeit a higher priority than traffic from a source which is non-critically blacklisted.
Although this allows traffic from different traffic sources to be handled differently, a considerable amount of searching may be required to identify a trie in which there is a match, if at all. This can slow down traffic-processing times, which is undesirable in most communication systems.
It would therefore be desirable to provide improved methods for searching, and storing data in, a database.